{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Two Sum II - Input Array Is Sorted"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #two-pointers #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #双指针 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: twoSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #两数之和 II - 输入有序数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>1</strong> 开始的整数数组&nbsp;<code>numbers</code> ，该数组已按<strong><em> </em>非递减顺序排列&nbsp; </strong>，请你从数组中找出满足相加之和等于目标数&nbsp;<code>target</code> 的两个数。如果设这两个数分别是 <code>numbers[index<sub>1</sub>]</code> 和 <code>numbers[index<sub>2</sub>]</code> ，则 <code>1 &lt;= index<sub>1</sub> &lt; index<sub>2</sub> &lt;= numbers.length</code> 。</p>\n",
    "\n",
    "<p>以长度为 2 的整数数组 <code>[index<sub>1</sub>, index<sub>2</sub>]</code> 的形式返回这两个整数的下标 <code>index<sub>1</sub></code><em> </em>和<em> </em><code>index<sub>2</sub></code>。</p>\n",
    "\n",
    "<p>你可以假设每个输入 <strong>只对应唯一的答案</strong> ，而且你 <strong>不可以</strong> 重复使用相同的元素。</p>\n",
    "\n",
    "<p>你所设计的解决方案必须只使用常量级的额外空间。</p>\n",
    "&nbsp;\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>numbers = [<strong><em>2</em></strong>,<strong><em>7</em></strong>,11,15], target = 9\n",
    "<strong>输出：</strong>[1,2]\n",
    "<strong>解释：</strong>2 与 7 之和等于目标数 9 。因此 index<sub>1</sub> = 1, index<sub>2</sub> = 2 。返回 [1, 2] 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>numbers = [<strong><em>2</em></strong>,3,<strong><em>4</em></strong>], target = 6\n",
    "<strong>输出：</strong>[1,3]\n",
    "<strong>解释：</strong>2 与 4 之和等于目标数 6 。因此 index<sub>1</sub> = 1, index<sub>2</sub> = 3 。返回 [1, 3] 。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>numbers = [<strong><em>-1</em></strong>,<strong><em>0</em></strong>], target = -1\n",
    "<strong>输出：</strong>[1,2]\n",
    "<strong>解释：</strong>-1 与 0 之和等于目标数 -1 。因此 index<sub>1</sub> = 1, index<sub>2</sub> = 2 。返回 [1, 2] 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= numbers.length &lt;= 3 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>-1000 &lt;= numbers[i] &lt;= 1000</code></li>\n",
    "\t<li><code>numbers</code> 按 <strong>非递减顺序</strong> 排列</li>\n",
    "\t<li><code>-1000 &lt;= target &lt;= 1000</code></li>\n",
    "\t<li><strong>仅存在一个有效答案</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [two-sum-ii-input-array-is-sorted](https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [two-sum-ii-input-array-is-sorted](https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,7,11,15]\\n9', '[2,3,4]\\n6', '[-1,0]\\n-1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        def dfs(node, arr):\n",
    "            if not node:\n",
    "                return\n",
    "            dfs(node.left, arr)\n",
    "            arr.append(node.val)\n",
    "            dfs(node.right, arr)\n",
    "        a = []\n",
    "        b = []\n",
    "        dfs(root1, a)\n",
    "        dfs(root2, b)\n",
    "        def find(arr, val):\n",
    "            index = bisect_left(arr, val)\n",
    "            if index != len(arr) and arr[index] == val:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        for i in a:\n",
    "            if find(b, target - i):\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        dic = {}\n",
    "        s = [root1]\n",
    "        while s:\n",
    "            now = s.pop()\n",
    "            dic[target-now.val] = 0\n",
    "            if now.left:\n",
    "                s.append(now.left)\n",
    "            if now.right:\n",
    "                s.append(now.right)\n",
    "        \n",
    "        s = [root2]\n",
    "        while s:\n",
    "            now = s.pop()\n",
    "            if now.val in dic:\n",
    "                return True\n",
    "            if now.left:\n",
    "                s.append(now.left)\n",
    "            if now.right:\n",
    "                s.append(now.right)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        it1 = TreeIterator(root1)\n",
    "        it2 = TreeIterator(root2, True)\n",
    "\n",
    "        while it1.has_next() and it2.has_next():\n",
    "            _sum = it1.peek() + it2.peek()\n",
    "            if _sum == target:\n",
    "                return True\n",
    "            elif _sum < target:\n",
    "                it1.next()\n",
    "            elif _sum > target:\n",
    "                it2.next()\n",
    "\n",
    "        return False\n",
    "\n",
    "class TreeIterator:\n",
    "    def __init__(self, root, reverse=False):\n",
    "        self.stk = []\n",
    "        self.reverse = reverse\n",
    "        if not self.reverse:\n",
    "            self.push_left_branch(root)\n",
    "        else:\n",
    "            self.push_right_branch(root)\n",
    "\n",
    "    def push_left_branch(self, root):\n",
    "        while root:\n",
    "            self.stk.append(root)\n",
    "            root = root.left\n",
    "\n",
    "    def push_right_branch(self, root):\n",
    "        while root:\n",
    "            self.stk.append(root)\n",
    "            root = root.right\n",
    "\n",
    "    def has_next(self):\n",
    "        return len(self.stk) > 0\n",
    "\n",
    "    def peek(self):\n",
    "        return self.stk[-1].val\n",
    "\n",
    "    def next(self):\n",
    "        cur = self.stk.pop()\n",
    "        if not self.reverse:\n",
    "            self.push_left_branch(cur.right)\n",
    "        else:\n",
    "            self.push_right_branch(cur.left)\n",
    "        return cur.val\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        stack1, stack2 = [], []\n",
    "        while True:\n",
    "            while root1:\n",
    "                stack1.append(root1)\n",
    "                root1 = root1.left\n",
    "            while root2:\n",
    "                stack2.append(root2)\n",
    "                root2 = root2.right\n",
    "            if not stack1 or not stack2:\n",
    "                return False\n",
    "            if stack1[-1].val + stack2[-1].val == target:\n",
    "                return True\n",
    "            elif stack1[-1].val + stack2[-1].val > target:\n",
    "                root2 = stack2[-1].left\n",
    "                stack2.pop()\n",
    "            else:\n",
    "                root1 = stack1[-1].right\n",
    "                stack1.pop()\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        stack1, stack2 = [], []\n",
    "\n",
    "        while True:\n",
    "            while root1:\n",
    "                stack1.append(root1)\n",
    "                root1 = root1.left\n",
    "            while root2:\n",
    "                stack2.append(root2)\n",
    "                root2 = root2.right\n",
    "\n",
    "            if not stack1 or not stack2:\n",
    "                break\n",
    "\n",
    "            node1, node2 = stack1[-1], stack2[-1]\n",
    "            curr_sum = node1.val + node2.val\n",
    "\n",
    "            if curr_sum == target:\n",
    "                return True\n",
    "            elif curr_sum < target:\n",
    "                stack1.pop()\n",
    "                root1 = node1.right\n",
    "            else:\n",
    "                stack2.pop()\n",
    "                root2 = node2.left\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        \n",
    "        def inorder(node):\n",
    "            if not node:\n",
    "                return []\n",
    "            \n",
    "            stack = []\n",
    "            cur = node\n",
    "            anw = []\n",
    "            while cur or stack:\n",
    "                if cur:\n",
    "                    stack.append(cur)\n",
    "                    cur = cur.left\n",
    "                else:\n",
    "                    cur = stack.pop()\n",
    "                    anw.append(cur.val)\n",
    "                    cur = cur.right\n",
    "            \n",
    "            return anw\n",
    "        \n",
    "        t1 = inorder(root1)\n",
    "        t2 = inorder(root2)\n",
    "        # combine = copy.deepcopy(t1)\n",
    "        # combine.extend(t2)\n",
    "        hashmap = collections.defaultdict(list)\n",
    "        for num in t1:\n",
    "            hashmap[num].append(1)\n",
    "        for num in t2:\n",
    "            hashmap[num].append(2)\n",
    "            if target - num in hashmap and hashmap[target-num][0] != hashmap[num][0]:\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        if not root1 or not root2:\n",
    "            return False\n",
    "        def dfs(root, target):\n",
    "            if not root:\n",
    "                return False\n",
    "            if root.val == target:\n",
    "                return True \n",
    "            elif root.val < target:\n",
    "                return dfs(root.right, target)\n",
    "            else:\n",
    "                return dfs(root.left, target)\n",
    "\n",
    "        return dfs(root1, target-root2.val) or self.twoSumBSTs(root1, root2.left, target) or self.twoSumBSTs(root1, root2.right, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        self.target = target\n",
    "        return self.subTwoSumBSTs(root1, root2, None, None, None, None)\n",
    "    \n",
    "    def subTwoSumBSTs(self, node1: Optional[TreeNode], node2: Optional[TreeNode], \n",
    "        val1_l: int, val1_h: int, val2_l: int, val2_h: int) -> bool:\n",
    "        if node1==None:\n",
    "            if (val1_l!=None and val2_l!=None and val1_l+val2_l==self.target) \\\n",
    "            or (val1_l!=None and val2_h!=None and val1_l+val2_h==self.target) \\\n",
    "            or (val1_h!=None and val2_l!=None and val1_h+val2_l==self.target) \\\n",
    "            or (val1_h!=None and val2_h!=None and val1_h+val2_h==self.target):\n",
    "                return True\n",
    "            else:\n",
    "                return self.sumValBST(val1_l, node2) or self.sumValBST(val1_h, node2)\n",
    "        if node2==None:\n",
    "            if (val1_l!=None and val2_l!=None and val1_l+val2_l==self.target) \\\n",
    "            or (val1_l!=None and val2_h!=None and val1_l+val2_h==self.target) \\\n",
    "            or (val1_h!=None and val2_l!=None and val1_h+val2_l==self.target) \\\n",
    "            or (val1_h!=None and val2_h!=None and val1_h+val2_h==self.target):\n",
    "                return True\n",
    "            else:\n",
    "                return self.sumValBST(val2_l, node1) or self.sumValBST(val2_h, node1) \n",
    "        \n",
    "        if node1.val + node2.val < self.target:\n",
    "            return self.subTwoSumBSTs(node1.right, node2.right, node1.val, val1_h, node2.val, val2_h) \\\n",
    "            or self.subTwoSumBSTs(node1.left, node2.right, val1_l, node1.val, node2.val, val2_h) \\\n",
    "            or self.subTwoSumBSTs(node1.right, node2.left, node1.val, val1_h, val2_l, node2.val)\n",
    "        elif node1.val + node2.val > self.target:\n",
    "            return self.subTwoSumBSTs(node1.left, node2.left, val1_l, node1.val, val2_l, node2.val) \\\n",
    "            or self.subTwoSumBSTs(node1.left, node2.right, val1_l, node1.val, node2.val, val2_h) \\\n",
    "            or self.subTwoSumBSTs(node1.right, node2.left, node1.val, val1_h, val2_l, node2.val)\n",
    "        else:\n",
    "            return True\n",
    "    \n",
    "    def sumValBST(self, val: int, node: Optional[TreeNode]) -> bool:\n",
    "        if node == None or val == None:\n",
    "            return False\n",
    "        \n",
    "        if val + node.val < self.target:\n",
    "            return self.sumValBST(val, node.right)\n",
    "        elif val + node.val > self.target:\n",
    "            return self.sumValBST(val, node.left)\n",
    "        else:\n",
    "            return True\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "def inorder(node:TreeNode, li:list):\n",
    "    if node == None:\n",
    "        return\n",
    "    inorder(node.left, li)\n",
    "    li.append(node.val)\n",
    "    inorder(node.right, li)\n",
    "\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: TreeNode, root2: TreeNode, target: int) -> bool:\n",
    "        li_1, li_2 = [], []\n",
    "        inorder(root1, li_1)\n",
    "        inorder(root2, li_2)\n",
    "        p1, p2, len1 = 0, len(li_2) -1, len(li_1)\n",
    "        \n",
    "        while p1 < len1 and p2 >=0:\n",
    "            judge = li_1[p1] + li_2[p2] - target\n",
    "            if judge == 0:\n",
    "                return True\n",
    "            elif judge > 0:\n",
    "                p2 -= 1\n",
    "            else:\n",
    "                p1 += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "def inorder(node:TreeNode, li:list):\n",
    "    if node == None:\n",
    "        return\n",
    "    inorder(node.left, li)\n",
    "    li.append(node.val)\n",
    "    inorder(node.right, li)\n",
    "\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: TreeNode, root2: TreeNode, target: int) -> bool:\n",
    "        li_1, li_2 = [], []\n",
    "        inorder(root1, li_1)\n",
    "        inorder(root2, li_2)\n",
    "        p1, p2, len1 = 0, len(li_2) -1, len(li_1)\n",
    "        \n",
    "        while p1 < len1 and p2 >=0:\n",
    "            judge = li_1[p1] + li_2[p2] - target\n",
    "            if judge == 0:\n",
    "                return True\n",
    "            elif judge > 0:\n",
    "                p2 -= 1\n",
    "            else:\n",
    "                p1 += 1\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        def preorder(node,res):\n",
    "            if node is None:\n",
    "                return\n",
    "            preorder(node.left, res)\n",
    "            res.append(node.val)\n",
    "            preorder(node.right, res)\n",
    "            return res\n",
    "        nums1, nums2 = preorder(root1,[]), preorder(root2,[])\n",
    "        for num in nums1:\n",
    "            index = bisect_left(nums2,target - num)\n",
    "            #print(num, index, target - num)\n",
    "            if index < len(nums2) and nums2[index] == (target - num):\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "def inorder(node:TreeNode, li:list):\n",
    "    if node == None:\n",
    "        return\n",
    "    inorder(node.left, li)\n",
    "    li.append(node.val)\n",
    "    inorder(node.right, li)\n",
    "\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: TreeNode, root2: TreeNode, target: int) -> bool:\n",
    "        li_1, li_2 = [], []\n",
    "        inorder(root1, li_1)\n",
    "        inorder(root2, li_2)\n",
    "        p1, p2, len1 = 0, len(li_2) -1, len(li_1)\n",
    "        \n",
    "        while p1 < len1 and p2 >=0:\n",
    "            judge = li_1[p1] + li_2[p2] - target\n",
    "            if judge == 0:\n",
    "                return True\n",
    "            elif judge > 0:\n",
    "                p2 -= 1\n",
    "            else:\n",
    "                p1 += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        a, b = [], []\n",
    "        self.VinOrder(root1, a)\n",
    "        self.VinOrder(root2, b)\n",
    "        an, bn = len(a), len(b)\n",
    "        #print(a,b)\n",
    "        i = 0\n",
    "        j = bn -1\n",
    "        while i < an and j>= 0:\n",
    "            if a[i] + b[j] == target:\n",
    "                return True\n",
    "            elif a[i] + b[j] < target:\n",
    "                i += 1\n",
    "            else:\n",
    "                j -= 1\n",
    "        return False\n",
    "    \n",
    "    def VinOrder(self, root, res:List[int]) -> None:\n",
    "        if not root:\n",
    "            return\n",
    "        self.VinOrder(root.left, res)\n",
    "        res.append(root.val)\n",
    "        self.VinOrder(root.right, res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def dfs(self, node, res):\n",
    "        if not node:\n",
    "            return\n",
    "        self.dfs(node.left, res)\n",
    "        res.append(node.val)\n",
    "        self.dfs(node.right, res)\n",
    "        return res\n",
    "    \n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        res1, res2 = [], []\n",
    "        res1 , res2 = self.dfs(root1, res1), self.dfs(root2, res2)\n",
    "        l1, l2, i1, i2 = len(res1), len(res2), 0, len(res2) - 1\n",
    "        while i1 < l1 and i2 > 0:\n",
    "            if res1[i1] + res2[i2] == target:\n",
    "                return True\n",
    "            elif res1[i1] + res2[i2] < target:\n",
    "                i1 += 1\n",
    "            elif res1[i1] + res2[i2] > target:\n",
    "                i2 -= 1\n",
    "        return False\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        '''def search2(root2, res):\n",
    "            if not root2: return False\n",
    "            if root2.val==res: return True\n",
    "            return search2(root2.right, res) or search2(root2.left, res)\n",
    "\n",
    "\n",
    "        def dfs(root, root2):\n",
    "            if not root: return False\n",
    "            if dfs(root.right, root2):\n",
    "                return True\n",
    "\n",
    "            if search2(root2, target-root.val):\n",
    "                return True\n",
    "\n",
    "            if dfs(root.left, root2):\n",
    "                return True\n",
    "\n",
    "            return False\n",
    "\n",
    "        return dfs(root1, root2)'''\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "def inorder(root, ls):\n",
    "            if not root:\n",
    "                return\n",
    "            inorder(root.left, ls)\n",
    "            ls.append(root.val)\n",
    "            inorder(root.right, ls)\n",
    "\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        ls1, ls2 = [], []\n",
    "        inorder(root1, ls1)\n",
    "        inorder(root2, ls2)\n",
    "\n",
    "        p1, p2, = 0, len(ls2) - 1\n",
    "        while p1 < len(ls1) and p2 >= 0:\n",
    "            flag = ls1[p1] + ls2[p2] - target\n",
    "            if flag == 0:\n",
    "                return True\n",
    "            elif flag > 0:\n",
    "                p2 -= 1\n",
    "            else:\n",
    "                p1 += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: TreeNode, root2: TreeNode, target: int) -> bool:\n",
    "        res1 = []\n",
    "        res2 = []\n",
    "        def dfs1(root):\n",
    "            if not root:\n",
    "                return\n",
    "            dfs1(root.left)\n",
    "            res1.append(root.val)\n",
    "            dfs1(root.right)\n",
    "        def dfs2(root):\n",
    "            if not root:\n",
    "                return\n",
    "            dfs2(root.right)\n",
    "            res2.append(root.val)\n",
    "            dfs2(root.left)\n",
    "        dfs1(root1)\n",
    "        dfs2(root2)\n",
    "        len1, len2 = len(res1), len(res2)\n",
    "        p1, p2 = 0, 0\n",
    "        while p1 < len1 and p2 < len2:\n",
    "            print(res1[p1], res2[p2])\n",
    "            ans = res1[p1] + res2[p2]\n",
    "            if ans == target:\n",
    "                return True\n",
    "            elif ans < target:\n",
    "                p1 += 1\n",
    "            else:\n",
    "                p2 += 1\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        \n",
    "        left_map = {}\n",
    "        right_map ={}\n",
    "        def dfs1(root):\n",
    "            if root == None:\n",
    "                return\n",
    "            dfs1(root.left)\n",
    "            dfs1(root.right)\n",
    "            left_map[root.val] = 0\n",
    "        \n",
    "        def dfs2(root):\n",
    "            if root == None:\n",
    "                return\n",
    "            dfs2(root.left)\n",
    "            dfs2(root.right)\n",
    "            right_map[root.val] = 0\n",
    "\n",
    "        dfs1(root1)\n",
    "        dfs2(root2)\n",
    "\n",
    "        for key in left_map.keys():\n",
    "            if target - key in right_map.keys():\n",
    "                return True\n",
    "        \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        \n",
    "        left_map = {}\n",
    "        right_map ={}\n",
    "        def dfs1(root):\n",
    "            if root == None:\n",
    "                return\n",
    "            dfs1(root.left)\n",
    "            dfs1(root.right)\n",
    "            left_map[root.val] = 0\n",
    "        \n",
    "        def dfs2(root):\n",
    "            if root == None:\n",
    "                return\n",
    "            dfs2(root.left)\n",
    "            dfs2(root.right)\n",
    "            right_map[root.val] = 0\n",
    "\n",
    "        dfs1(root1)\n",
    "        dfs2(root2)\n",
    "\n",
    "        for key in left_map.keys():\n",
    "            if target - key in right_map.keys():\n",
    "                return True\n",
    "        \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "def inorder(node:TreeNode, li:list,target):\n",
    "    if node == None:\n",
    "        return\n",
    "    inorder(node.left, li,target)\n",
    "    li.append(target-node.val)\n",
    "    inorder(node.right, li,target)\n",
    "\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: TreeNode, root2: TreeNode, target: int) -> bool:\n",
    "        li_1=[]\n",
    "        inorder(root1, li_1, target)\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return False\n",
    "            if node.val in li_1:\n",
    "                return True\n",
    "            else: \n",
    "                return dfs(node.left) or dfs(node.right)\n",
    "        return dfs(root2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "def inorder(node:TreeNode, li:list,target):\n",
    "    if node == None:\n",
    "        return\n",
    "    inorder(node.left, li,target)\n",
    "    li.append(target-node.val)\n",
    "    inorder(node.right, li,target)\n",
    "\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: TreeNode, root2: TreeNode, target: int) -> bool:\n",
    "        li_1=[]\n",
    "        inorder(root1, li_1, target)\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return False\n",
    "            if node.val in li_1:\n",
    "                return True\n",
    "            else: \n",
    "                return dfs(node.left) or dfs(node.right)\n",
    "        return dfs(root2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        def preo2(n, v):\n",
    "            if n.val == v: return True\n",
    "            if n.val > v and n.left:\n",
    "                return preo2(n.left, v)\n",
    "            if n.val < v and n.right:\n",
    "                return preo2(n.right, v)\n",
    "            return False\n",
    "\n",
    "        def preo1(n):\n",
    "            if preo2(root2, target-n.val): return True\n",
    "\n",
    "            if n.left:\n",
    "                if preo1(n.left): return True\n",
    "\n",
    "            if n.right:\n",
    "                if preo1(n.right): return True\n",
    "\n",
    "            return False\n",
    "\n",
    "        return preo1(root1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        arr1, arr2 = [], []\n",
    "        def dfs(node: Optional[TreeNode], arr: list[int]):\n",
    "            if node:\n",
    "                dfs(node.left, arr)\n",
    "                arr.append(node.val)\n",
    "                dfs(node.right, arr)\n",
    "\n",
    "        dfs(root1, arr1)\n",
    "        dfs(root2, arr2)\n",
    "\n",
    "        n, m = len(arr1), len(arr2)\n",
    "        i, j = 0, m - 1\n",
    "\n",
    "        while i < n and j >= 0:\n",
    "            res = arr1[i] + arr2[j]\n",
    "            if res == target:\n",
    "                return True\n",
    "            elif res > target:\n",
    "                j -= 1\n",
    "            else:\n",
    "                i += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "def inorder(node:TreeNode, li:list,target):\n",
    "    if node == None:\n",
    "        return\n",
    "    inorder(node.left, li,target)\n",
    "    li.append(target-node.val)\n",
    "    inorder(node.right, li,target)\n",
    "\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: TreeNode, root2: TreeNode, target: int) -> bool:\n",
    "        li_1=[]\n",
    "        inorder(root1, li_1, target)\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return False\n",
    "            if node.val in li_1:\n",
    "                return True\n",
    "            else: \n",
    "                return dfs(node.left) or dfs(node.right)\n",
    "        return dfs(root2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        pre2=[]\n",
    "        #中序遍历\n",
    "        def dfs(x):\n",
    "            if x:\n",
    "                dfs(x.left)\n",
    "                pre2.append(x.val)\n",
    "                dfs(x.right)\n",
    "        dfs(root1)\n",
    "        pre1=pre2.copy()\n",
    "        pre2.clear()\n",
    "        dfs(root2)\n",
    "        #双指针搜索即可\n",
    "        i,j=0,len(pre2)-1\n",
    "        while i<len(pre1) and j>=0:\n",
    "            cur=pre1[i]+pre2[j]\n",
    "            if cur<target:\n",
    "                i+=1\n",
    "            elif cur>target:\n",
    "                j-=1\n",
    "            else:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "      def search(root, val):\n",
    "        if not root:\n",
    "          return False\n",
    "        \n",
    "        if root.val + val == target:\n",
    "          return True\n",
    "        \n",
    "        if root.val + val > target:\n",
    "          return search(root.left, val)\n",
    "        else:\n",
    "          return search(root.right, val)\n",
    "        \n",
    "      def dfs(root):\n",
    "        if not root:\n",
    "          return False\n",
    "        \n",
    "        if search(root2, root.val):\n",
    "          return True\n",
    "        \n",
    "        return dfs(root.left) or dfs(root.right)\n",
    "      \n",
    "      return dfs(root1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        a, b = [], []\n",
    "        self.VinOrder(root1, a)\n",
    "        self.VinOrder(root2, b)\n",
    "        an, bn = len(a), len(b)\n",
    "        #print(a,b)\n",
    "        i = 0\n",
    "        j = bn -1\n",
    "        while i < an and j>= 0:\n",
    "            if a[i] + b[j] == target:\n",
    "                return True\n",
    "            elif a[i] + b[j] < target:\n",
    "                i += 1\n",
    "            else:\n",
    "                j -= 1\n",
    "        return False\n",
    "    \n",
    "    def VinOrder(self, root, res:List[int]) -> None:\n",
    "        if not root:\n",
    "            return\n",
    "        self.VinOrder(root.left, res)\n",
    "        res.append(root.val)\n",
    "        self.VinOrder(root.right, res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def is_val_in_tree(self, root, val):\n",
    "        if not root:\n",
    "            return False\n",
    "        if root.val == val:\n",
    "            return True\n",
    "        elif root.val < val:\n",
    "            return self.is_val_in_tree(root.right, val)\n",
    "        elif root.val > val:\n",
    "            return self.is_val_in_tree(root.left, val)\n",
    "\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        if not root1:\n",
    "            return False\n",
    "        return self.is_val_in_tree(root2, target - root1.val) or self.twoSumBSTs(root1.left, root2, target) or self.twoSumBSTs(root1.right, root2, target)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        \n",
    "        def listtree(root,l):\n",
    "            if root:\n",
    "                l.append(root.val)\n",
    "                if root.left:\n",
    "                    l.append(root.left.val)\n",
    "                    listtree(root.left,l)\n",
    "                if root.right:\n",
    "                    l.append(root.right.val)\n",
    "                    listtree(root.right,l)\n",
    "                return l\n",
    "            else:\n",
    "                return l\n",
    "        l1 = listtree(root1,[])\n",
    "        l2 = listtree(root2,[])\n",
    "        for i in l1:\n",
    "            if target-i in l2:\n",
    "                return True\n",
    "        return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        res1, res2 = [], []\n",
    "        def dfs1(root):\n",
    "            if not root: return\n",
    "            dfs1(root.left)\n",
    "            res1.append(root.val)\n",
    "            dfs1(root.right)\n",
    "        \n",
    "        def dfs2(root):\n",
    "            if not root: return\n",
    "            dfs2(root.left)\n",
    "            res2.append(root.val)\n",
    "            dfs2(root.right)\n",
    "        \n",
    "        dfs1(root1)\n",
    "        dfs2(root2)\n",
    "        for x in res1:\n",
    "            for y in res2:\n",
    "                if x + y == target: return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "      def search(root, val):\n",
    "        if not root:\n",
    "          return False\n",
    "        \n",
    "        if root.val + val == target:\n",
    "          return True\n",
    "        \n",
    "        if root.val + val > target:\n",
    "          return search(root.left, val)\n",
    "        else:\n",
    "          return search(root.right, val)\n",
    "        \n",
    "      def dfs(root):\n",
    "        if not root:\n",
    "          return False\n",
    "        \n",
    "        if search(root2, root.val):\n",
    "          return True\n",
    "        \n",
    "        return dfs(root.left) or dfs(root.right)\n",
    "      \n",
    "      return dfs(root1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "      def search(root, val):\n",
    "        if not root:\n",
    "          return False\n",
    "        \n",
    "        if root.val + val == target:\n",
    "          return True\n",
    "        \n",
    "        if root.val + val > target:\n",
    "          return search(root.left, val)\n",
    "        else:\n",
    "          return search(root.right, val)\n",
    "        \n",
    "      def dfs(root):\n",
    "        if not root:\n",
    "          return False\n",
    "        \n",
    "        if search(root2, root.val):\n",
    "          return True\n",
    "        \n",
    "        return dfs(root.left) or dfs(root.right)\n",
    "      \n",
    "      return dfs(root1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        def inorder(node,res):\n",
    "            if node is None:\n",
    "                return\n",
    "            inorder(node.left, res)\n",
    "            res.append(node.val)\n",
    "            inorder(node.right, res)\n",
    "            return res\n",
    "        nums1, nums2 = inorder(root1,[]), inorder(root2,[])\n",
    "        for num in nums1:\n",
    "            index = bisect_left(nums2,target - num)\n",
    "            if index < len(nums2) and nums2[index] == (target - num):\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        def dfs(node: TreeNode, res: List[int]):\n",
    "            if not node:\n",
    "                return\n",
    "            dfs(node.left,  res)\n",
    "            res.append(node.val)\n",
    "            dfs(node.right, res)\n",
    "\n",
    "        a, b = [], []\n",
    "        dfs(root1, a)\n",
    "        dfs(root2, b)\n",
    "        m, n = len(a), len(b)\n",
    "\n",
    "        i, j = 0, n -1 \n",
    "        while i < m and 0 <= j:\n",
    "            if a[i] + b[j] == target:\n",
    "                return True\n",
    "            elif a[i] + b[j] < target:\n",
    "                i += 1\n",
    "            else:\n",
    "                j -= 1  \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        # 遍历两颗数，把值换成列表\n",
    "        l1 = []\n",
    "        l2 = []\n",
    "\n",
    "        def dfs(root,l):\n",
    "            if not root:\n",
    "                return \n",
    "            \n",
    "            left = dfs(root.left,l)\n",
    "            l.append(root.val)\n",
    "            right = dfs(root.right,l)\n",
    "\n",
    "            return root.val\n",
    "\n",
    "        dfs(root1,l1)\n",
    "        dfs(root2,l2)\n",
    "        # print(l1)\n",
    "        # print(l2)\n",
    "\n",
    "        s2 = set(l2)\n",
    "        for a in l1:\n",
    "            if target - a in s2:\n",
    "                return True\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        pre2=[]\n",
    "        #中序遍历\n",
    "        def dfs(x):\n",
    "            if x:\n",
    "                dfs(x.left)\n",
    "                pre2.append(x.val)\n",
    "                dfs(x.right)\n",
    "        dfs(root1)\n",
    "        pre1=pre2.copy()\n",
    "        pre2.clear()\n",
    "        dfs(root2)\n",
    "        #双指针搜索即可\n",
    "        i,j=0,len(pre2)-1\n",
    "        while i<len(pre1) and j>=0:\n",
    "            cur=pre1[i]+pre2[j]\n",
    "            if cur<target:\n",
    "                i+=1\n",
    "            elif cur>target:\n",
    "                j-=1\n",
    "            else:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "\n",
    "        def search2(root2, res):\n",
    "            if not root2: return False\n",
    "            if root2.val==res: return True\n",
    "            return search2(root2.right, res) or search2(root2.left, res)\n",
    "\n",
    "\n",
    "        def dfs(root, root2):\n",
    "            if not root: return False\n",
    "            if dfs(root.right, root2):\n",
    "                return True\n",
    "\n",
    "            if search2(root2, target-root.val):\n",
    "                return True\n",
    "\n",
    "            if dfs(root.left, root2):\n",
    "                return True\n",
    "\n",
    "            return False\n",
    "\n",
    "        return dfs(root1, root2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        tree1 = []\n",
    "        tree2 = []\n",
    "        def inorder(root: Optional[TreeNode], idx: int):\n",
    "            nonlocal tree1\n",
    "            nonlocal tree2\n",
    "            if not root:\n",
    "                return\n",
    "            inorder(root.left, idx)\n",
    "            if idx == 1:\n",
    "                tree1.append(root.val)\n",
    "            else:\n",
    "                tree2.append(root.val)\n",
    "            inorder(root.right, idx)\n",
    "        inorder(root1, 1)\n",
    "        inorder(root2, 2)\n",
    "\n",
    "        left = 0\n",
    "        right = len(tree2)-1\n",
    "        while left < len(tree1) and right >= 0:\n",
    "            tmp = tree1[left]+tree2[right]\n",
    "            if target == tmp:\n",
    "                return True\n",
    "            elif tmp < target:\n",
    "                left += 1\n",
    "            else:\n",
    "                right -= 1\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: TreeNode, root2: TreeNode, target: int) -> bool:\n",
    "        a, b = [], []\n",
    "        self.dfs_LNR(root1, a)\n",
    "        self.dfs_LNR(root2, b)\n",
    "        an, bn = len(a), len(b)\n",
    "        ######## 贪心，双指针，从两边向中间夹逼\n",
    "        i = 0\n",
    "        j = bn -1 \n",
    "        while i < an and 0 <= j:\n",
    "            if a[i] + b[j] == target:\n",
    "                return True\n",
    "            elif a[i] + b[j] < target:\n",
    "                i += 1\n",
    "            else:\n",
    "                j -= 1  \n",
    "        return False\n",
    "    ############ 二叉树 中序遍历 ############\n",
    "    def dfs_LNR(self, rt: TreeNode, res: List[int]) -> None:\n",
    "        if rt == None:\n",
    "            return\n",
    "        self.dfs_LNR(rt.left, res)\n",
    "        res.append(rt.val)\n",
    "        self.dfs_LNR(rt.right, res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        def dfs(root, res):\n",
    "            if not root: return None\n",
    "            dfs(root.left, res)\n",
    "            res.append(root.val)\n",
    "            dfs(root.right, res)\n",
    "\n",
    "        a, b = [], []\n",
    "        dfs(root1, a)\n",
    "        dfs(root2, b)\n",
    "        \n",
    "        an, bn = len(a), len(b)\n",
    "        i, j = 0, bn - 1\n",
    "        while i < an and 0 <= j:\n",
    "            if a[i] + b[j] == target:\n",
    "                return True\n",
    "            elif a[i] + b[j] < target:\n",
    "                i += 1\n",
    "            else:\n",
    "                j -= 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        def inorder(node, arr):\n",
    "            if not node:\n",
    "                return\n",
    "            inorder(node.left, arr)\n",
    "            arr.append(node.val)\n",
    "            inorder(node.right, arr)\n",
    "\n",
    "        arr1, arr2 = [], []\n",
    "        inorder(root1, arr1)\n",
    "        inorder(root2, arr2)\n",
    "    \n",
    "        i, j = 0, len(arr2) - 1\n",
    "    \n",
    "        while i < len(arr1) and j >= 0:\n",
    "            if arr1[i] + arr2[j] == target:\n",
    "                return True\n",
    "            elif arr1[i] + arr2[j] < target:\n",
    "                i += 1\n",
    "            else:\n",
    "                j -= 1\n",
    "    \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def inorder(self,node,li):\n",
    "        if node == None:\n",
    "            return \n",
    "        self.inorder(node.left,li) \n",
    "        li.append(node.val) \n",
    "        self.inorder(node.right,li)\n",
    "        return li\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        li_1,li_2 = [],[]\n",
    "        self.inorder(root1,li_1)\n",
    "        self.inorder(root2,li_2)\n",
    "        p1,p2,len1 =0,len(li_2)-1,len(li_1)\n",
    "        while p1 < len1 and p2 >= 0:\n",
    "            judge = li_1[p1] + li_2[p2] - target\n",
    "            if judge == 0:\n",
    "                return True\n",
    "            elif judge > 0:\n",
    "                p2 -= 1\n",
    "            else:\n",
    "                p1 += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def inorder(self,node,li):\n",
    "        if node == None:\n",
    "            return \n",
    "        self.inorder(node.left,li) \n",
    "        li.append(node.val) \n",
    "        self.inorder(node.right,li)\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        li_1,li_2 = [],[]\n",
    "        self.inorder(root1,li_1)\n",
    "        self.inorder(root2,li_2)\n",
    "        p1,p2,len1 =0,len(li_2)-1,len(li_1)\n",
    "        while p1 < len1 and p2 >= 0:\n",
    "            judge = li_1[p1] + li_2[p2] - target\n",
    "            if judge == 0:\n",
    "                return True\n",
    "            elif judge > 0:\n",
    "                p2 -= 1\n",
    "            else:\n",
    "                p1 += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "      def search(root, val):\n",
    "        if not root:\n",
    "          return False\n",
    "        \n",
    "        if root.val + val == target:\n",
    "          return True\n",
    "        \n",
    "        if root.val + val > target:\n",
    "          return search(root.left, val)\n",
    "        else:\n",
    "          return search(root.right, val)\n",
    "        \n",
    "      def dfs(root):\n",
    "        if not root:\n",
    "          return False\n",
    "        \n",
    "        if search(root2, root.val):\n",
    "          return True\n",
    "        \n",
    "        return dfs(root.left) or dfs(root.right)\n",
    "      \n",
    "      return dfs(root1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        def inorder(root, order):\n",
    "            if not root:\n",
    "                return\n",
    "            inorder(root.left, order)\n",
    "            order.append(root.val)\n",
    "            inorder(root.right, order)\n",
    "        \n",
    "        order1, order2 = [], []\n",
    "        inorder(root1, order1)\n",
    "        inorder(root2, order2)\n",
    "\n",
    "        i, j = 0, len(order2) - 1\n",
    "        while i < len(order1) and j >= 0:\n",
    "            if order1[i] + order2[j] == target:\n",
    "                return True\n",
    "            elif order1[i] + order2[j] > target:\n",
    "                j -= 1\n",
    "            else:\n",
    "                i += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    def twoSumBSTs(self, root1: TreeNode, root2: TreeNode, target: int) -> bool:\r\n",
    "        a, b = [], []\r\n",
    "        self.dfs_LNR(root1, a)\r\n",
    "        self.dfs_LNR(root2, b)\r\n",
    "        an, bn = len(a), len(b)\r\n",
    "        ######## 贪心，双指针，从两边向中间夹逼\r\n",
    "        i = 0\r\n",
    "        j = bn -1 \r\n",
    "        while i < an and 0 <= j:\r\n",
    "            if a[i] + b[j] == target:\r\n",
    "                return True\r\n",
    "            elif a[i] + b[j] < target:\r\n",
    "                i += 1\r\n",
    "            else:\r\n",
    "                j -= 1  \r\n",
    "        return False\r\n",
    "    ############ 二叉树 中序遍历 ############\r\n",
    "    def dfs_LNR(self, rt: TreeNode, res: List[int]) -> None:\r\n",
    "        if rt == None:\r\n",
    "            return\r\n",
    "        self.dfs_LNR(rt.left, res)\r\n",
    "        res.append(rt.val)\r\n",
    "        self.dfs_LNR(rt.right, res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    \n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        def searchValue(root: Optional[TreeNode], value: int) -> bool:\n",
    "            if root == None:\n",
    "                return False\n",
    "            if root.val == value:\n",
    "                return True\n",
    "            if root.val > value:\n",
    "                return searchValue(root.left, value)\n",
    "            else:\n",
    "                return searchValue(root.right, value)\n",
    "            return False\n",
    "\n",
    "        def searchNode(root1, root2, target) -> bool:\n",
    "            if root1 == None:\n",
    "                return False\n",
    "            return searchValue(root2, target - root1.val) or searchNode(root1.left, root2, target) or searchNode(root1.right, root2, target)\n",
    "        \n",
    "        return searchNode(root1, root2, target)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        def checkPair(node, target2):\n",
    "            if not node:\n",
    "                return False\n",
    "            if node.val == target2:\n",
    "                return True\n",
    "            if node.val < target2:\n",
    "                return checkPair(node.right, target2)\n",
    "            else:\n",
    "                return checkPair(node.left, target2)\n",
    "\n",
    "        def inOrder(root1, root2, target):\n",
    "            if not root1:\n",
    "                return False\n",
    "            \n",
    "            if checkPair(root2, target - root1.val):\n",
    "                return True\n",
    "\n",
    "            return inOrder(root1.left, root2, target) or inOrder(root1.right, root2, target)\n",
    "\n",
    "        return inOrder(root1, root2, target)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: TreeNode, root2: TreeNode, target: int) -> bool:\n",
    "        # 将两个 BST 转化成两个有序数组\n",
    "        arr1 = self.traverse(root1)\n",
    "        arr2 = self.traverse(root2)\n",
    "        m, n = len(arr1), len(arr2)\n",
    "        # 对有序数组执行两数之和问题的算法逻辑\n",
    "        i, j = 0, n-1\n",
    "        while i < m and j >= 0:\n",
    "            sum = arr1[i] + arr2[j]\n",
    "            if sum < target:\n",
    "                # 让和大一些\n",
    "                i += 1\n",
    "            elif sum > target:\n",
    "                # 让和小一些\n",
    "                j -= 1\n",
    "            else:\n",
    "                # 找到和 target\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "    # 返回中序遍历结果\n",
    "    def traverse(self, root: TreeNode) -> List[int]:\n",
    "        res = []\n",
    "        if not root:\n",
    "            return res\n",
    "        res += self.traverse(root.left)\n",
    "        res.append(root.val)\n",
    "        res += self.traverse(root.right)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        def dfs(root: Optional[TreeNode], i: int):\n",
    "            if root is None:\n",
    "                return\n",
    "            dfs(root.left, i)\n",
    "            nums[i].append(root.val)\n",
    "            dfs(root.right, i)\n",
    "\n",
    "        nums = [[], []]\n",
    "        dfs(root1, 0)\n",
    "        dfs(root2, 1)\n",
    "        i, j = 0, len(nums[1]) - 1\n",
    "        while i < len(nums[0]) and ~j:\n",
    "            x = nums[0][i] + nums[1][j]\n",
    "            if x == target:\n",
    "                return True\n",
    "            if x < target:\n",
    "                i += 1\n",
    "            else:\n",
    "                j -= 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        \n",
    "        ans = False\n",
    "        \n",
    "        pre = set()\n",
    "        \n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return \n",
    "            lst1.append(node.val)\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "            return \n",
    "        \n",
    "        lst1 = []\n",
    "        dfs(root1)\n",
    "\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return\n",
    "            lst2.append(node.val)\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "            return\n",
    "\n",
    "        lst2 = []\n",
    "        dfs(root2)\n",
    "        pre = set(lst1)\n",
    "        for num in lst2:\n",
    "            if target-num in pre:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        # 用于存储第一棵树节点值的集合\n",
    "        values = set()\n",
    "        \n",
    "        # 从第一棵树中遍历所有节点并存入集合\n",
    "        def traverse(node):\n",
    "            if not node:\n",
    "                return\n",
    "            values.add(node.val)\n",
    "            traverse(node.left)\n",
    "            traverse(node.right)\n",
    "        \n",
    "        traverse(root1)\n",
    "        \n",
    "        # 用于检查第二棵树中是否有匹配的节点值\n",
    "        def check(node):\n",
    "            if not node:\n",
    "                return False\n",
    "            complement = target - node.val\n",
    "            if complement in values:\n",
    "                return True\n",
    "            return check(node.left) or check(node.right)\n",
    "        \n",
    "        return check(root2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "\n",
    "        self.ret = False\n",
    "        def visit(root1):\n",
    "            if not root1:\n",
    "                return\n",
    "            self.ret = self.ret or search(root2, target-root1.val)\n",
    "            if self.ret:\n",
    "                return\n",
    "            visit(root1.left)\n",
    "            visit(root1.right)\n",
    "\n",
    "        def search(root2, val):\n",
    "            if not root2:\n",
    "                return False\n",
    "            \n",
    "            if root2.val == val:\n",
    "                return True\n",
    "            \n",
    "            elif root2.val > val:\n",
    "                return search(root2.left, val)\n",
    "            else:\n",
    "                return search(root2.right, val)\n",
    "            \n",
    "\n",
    "        visit(root1)\n",
    "        return self.ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        res1, res2 = [], []\n",
    "        def dfs1(root):\n",
    "            if not root: return\n",
    "            dfs1(root.left)\n",
    "            res1.append(root.val)\n",
    "            dfs1(root.right)\n",
    "        \n",
    "        def dfs2(root):\n",
    "            if not root: return\n",
    "            dfs2(root.left)\n",
    "            res2.append(root.val)\n",
    "            dfs2(root.right)\n",
    "        \n",
    "        dfs1(root1)\n",
    "        dfs2(root2)\n",
    "        res1 = list(set(res1))\n",
    "        res2 = list(set(res2))\n",
    "        for x in res1:\n",
    "            for y in res2:\n",
    "                if x + y == target: return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        set1 = set()\n",
    "        set2 = set()\n",
    "        self.dfs(root1, set1, target)\n",
    "        self.dfs(root2, set2, target)\n",
    "        \n",
    "        for n in set1:\n",
    "            if (target - n) in set2:\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "    def dfs(self, node, s, target):\n",
    "        if node.left:\n",
    "            self.dfs(node.left, s, target)\n",
    "        s.add(node.val)\n",
    "        if node.right:\n",
    "            self.dfs(node.right, s, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "\n",
    "        line=set([])\n",
    "\n",
    "        def method(node):\n",
    "            nonlocal line\n",
    "            if not node:\n",
    "                return\n",
    "            else:\n",
    "                method(node.left)\n",
    "                line.add(node.val)\n",
    "                method(node.right)\n",
    "\n",
    "        def method_1(node):\n",
    "            nonlocal line\n",
    "            nonlocal target\n",
    "            if node==None:\n",
    "                return False\n",
    "            else:\n",
    "                left=method_1(node.left)\n",
    "                result=False\n",
    "                if (target-node.val) in line:\n",
    "                    result=True\n",
    "                right=method_1(node.right)\n",
    "\n",
    "                return (left or result or right)\n",
    "\n",
    "        method(root1)\n",
    "        return method_1(root2)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        m = set()\n",
    "        couple = set()\n",
    "\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return False\n",
    "\n",
    "            if target - root.val in couple:\n",
    "                return True\n",
    "\n",
    "            m.add(root.val)\n",
    "            return dfs(root.left) or dfs(root.right)\n",
    "\n",
    "        dfs(root1)\n",
    "        couple = m\n",
    "        return dfs(root2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:\n",
    "        def find(root, target):\n",
    "            if root == None:\n",
    "                return False\n",
    "            if root.val == target:\n",
    "                return True\n",
    "            elif root.val > target:\n",
    "                return find(root.left, target)\n",
    "            else:\n",
    "                return find(root.right, target)\n",
    "        \n",
    "        if root1 == None or root2 == None:\n",
    "            return False\n",
    "        return find(root2, target - root1.val) or self.twoSumBSTs(root1.left, root2, target) or self.twoSumBSTs(root1.right, root2, target)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, numbers: List[int], target: int) -> List[int]:\n",
    "        if numbers[0] > target: return []\n",
    "        # i = 0\n",
    "        # while i < len(numbers) and numbers[i] <= target:\n",
    "        #     if target - numbers[i] in numbers:\n",
    "        #         return [i+1, numbers[i+1:].index(target - numbers[i]) + i + 2]\n",
    "        #     i += 1\n",
    "        # return []\n",
    "        left, right = 0, len(numbers) - 1\n",
    "        while left < right:\n",
    "            num_sum = numbers[left] + numbers[right]\n",
    "            if num_sum == target:\n",
    "                return [left+1, right+1]\n",
    "            elif num_sum < target:\n",
    "                left += 1\n",
    "            else:\n",
    "                right -= 1\n",
    "        return []\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, numbers: 'List[int]', target: 'int') -> 'List[int]':\n",
    "        n = len(numbers)\n",
    "        i, j = 0, n - 1\n",
    "        while i < j:\n",
    "            s = numbers[i] + numbers[j]\n",
    "            if s == target:\n",
    "                return [i + 1, j + 1]\n",
    "            elif s > target:\n",
    "                j -= 1\n",
    "            else:\n",
    "                i += 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, numbers: 'List[int]', target: 'int') -> 'List[int]':\n",
    "        n = len(numbers)\n",
    "        i, j = 0, n - 1\n",
    "        while i < j:\n",
    "            s = numbers[i] + numbers[j]\n",
    "            if s == target:\n",
    "                return [i + 1, j + 1]\n",
    "            if s > target:\n",
    "                # j -= 1\n",
    "                l, r = i + 1, j\n",
    "                to_match = target - numbers[i]\n",
    "                while l <= r:\n",
    "                    c = l + (r - l) // 2\n",
    "                    if numbers[c] == to_match:\n",
    "                        r = c\n",
    "                        break\n",
    "                    elif numbers[c] < to_match:\n",
    "                        l = c + 1\n",
    "                    else:\n",
    "                        r = c - 1\n",
    "                j = r   \n",
    "            else:\n",
    "                # i += 1\n",
    "                l, r = i, j - 1\n",
    "                to_match = target - numbers[j]\n",
    "                while l <= r:\n",
    "                    c = l + (r - l) // 2\n",
    "                    if numbers[c] == to_match:\n",
    "                        l = c\n",
    "                        break\n",
    "                    elif numbers[c] < to_match:\n",
    "                        l = c + 1\n",
    "                    else:\n",
    "                        r = c - 1\n",
    "                i = l\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, numbers, target):\n",
    "        \"\"\"\n",
    "        :type numbers: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        l = 0\n",
    "        r = len(numbers) - 1\n",
    "        print(r)\n",
    "\n",
    "        while l<r:\n",
    "            if numbers[l] + numbers[r] == target:\n",
    "                return [l+1, r+1]\n",
    "                break\n",
    "            elif numbers[l] + numbers[r] < target:\n",
    "                l+=1\n",
    "            else:\n",
    "                r-=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, numbers, target):\n",
    "        \"\"\"\n",
    "        :type numbers: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        l = 0;h = len(numbers)-1\n",
    "        while l < h:\n",
    "            s = numbers[l] + numbers[h]\n",
    "            if s == target:\n",
    "                return [l+1,h+1]\n",
    "            elif s < target:\n",
    "                l += 1\n",
    "            else:\n",
    "                h -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, numbers: List[int], target: int) -> List[int]:\n",
    "        end = len(numbers)-1\n",
    "        start = 0\n",
    "        while end != start:\n",
    "            if(numbers[end] + numbers[start] == target):\n",
    "                return [start+1, end+1]\n",
    "            elif(numbers[end] + numbers[start] > target):\n",
    "                end -= 1\n",
    "            else:\n",
    "                start += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def bisearch(self, array,t):\n",
    "        l = 0\n",
    "        r = len(array)-1\n",
    "        \n",
    "        if t<array[0] or t> array[r]:\n",
    "            return -1\n",
    "        \n",
    "        while r>=l:\n",
    "            \n",
    "            m = (l+r)//2\n",
    "\n",
    "            if t>array[m]:\n",
    "                l = m+1\n",
    "            elif t<array[m]:\n",
    "                r = m-1\n",
    "            else:\n",
    "                return m\n",
    "        \n",
    "        return -1\n",
    "    \n",
    "    def twoSum(self, numbers, target):\n",
    "        \"\"\"\n",
    "        :type numbers: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        for index,n in enumerate(numbers[:-1]):\n",
    "            result = self.bisearch(numbers[index+1:], target-n)\n",
    "            if result != -1 :\n",
    "                return [index+1,index + result + 2]\n",
    "                \n",
    "        # for index,n in enumerate(numbers[:-1]):\n",
    "        #     try:\n",
    "        #         j = numbers[index+1:].index(target - n)\n",
    "        #         return [index+1, index+j + 2]\n",
    "        #     except ValueError:\n",
    "        #         continue\n",
    "            \n",
    "            \n",
    "            \n",
    "                \n",
    "            \n",
    "                \n",
    "       \n",
    "   \n",
    "        \n",
    "        \n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: 'List[int]', target: 'int') -> 'List[int]':\n",
    "        if not nums:\n",
    "            return None\n",
    "        dic = {}\n",
    "        for i, item in enumerate(nums):\n",
    "            temp = target - item\n",
    "            for key, value in dic.items():\n",
    "                if value == temp:\n",
    "                    return [key+1, i+1]\n",
    "            dic[i] = item\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, numbers, target):\n",
    "        \"\"\"\n",
    "        :type numbers: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        dic = dict()\n",
    "        for idx, val in enumerate(numbers):\n",
    "            if val in dic:\n",
    "                dic[val].append(idx)\n",
    "            else:\n",
    "                dic[val] = [idx]\n",
    "        print(dic)\n",
    "        for idx, val in enumerate(numbers):\n",
    "            sub = target - val\n",
    "            # print(val, sub)\n",
    "            if sub in dic:\n",
    "                if idx != dic[sub][0]:\n",
    "                    return [idx + 1, dic[sub][0] + 1]\n",
    "                elif len(dic[val]) > 1:\n",
    "                    return [idx + 1, dic[sub][1]+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, numbers, target):\n",
    "        \"\"\"\n",
    "        :type numbers: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        num = numbers\n",
    "        r,l = 0 ,len(num)-1\n",
    "        while r<l:\n",
    "            sum_ = num[r]+num[l]\n",
    "            print(r,l,num[r]+num[l],num[r],num[l])\n",
    "            if sum_== target:\n",
    "                return  [r+1,l+1]\n",
    "            elif sum_ <target:\n",
    "                r=r+1\n",
    "            else:\n",
    "                l=l-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, numbers, target):\n",
    "        \"\"\"\n",
    "        :type numbers: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        nums = [(i+1, numbers[i]) for i in range(len(numbers))]\n",
    "        nums.sort(key=lambda elem: elem[1])\n",
    "        nums.sort(key=lambda elem: elem[0])\n",
    "        for i in range(len(nums)):\n",
    "            ans = self.binsearch(nums, target-nums[i][1], i+1)\n",
    "            if ans is not None:\n",
    "                return (nums[i][0], ans)\n",
    "        return nums\n",
    "    \n",
    "    def binsearch(self, nums, target, l):\n",
    "        ans = None\n",
    "        r = len(nums)\n",
    "        while l <= r and l < len(nums):\n",
    "            idx = int((l + r) / 2)\n",
    "            if nums[idx][1] == target:\n",
    "                ans = nums[idx][0]\n",
    "                r = idx - 1\n",
    "            elif nums[idx][1] < target:\n",
    "                l = idx + 1\n",
    "            else:\n",
    "                r = idx - 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, numbers: 'List[int]', target: 'int') -> 'List[int]':\n",
    "        dic = {}\n",
    "        for i in range(len(numbers)):\n",
    "            \n",
    "            if numbers[i] in dic.keys():\n",
    "                if i+1!=dic[numbers[i]]:\n",
    "                    return [dic[numbers[i]],i+1]\n",
    "            dic[target - numbers[i]] = (i+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, numbers: 'List[int]', target: 'int') -> 'List[int]':\n",
    "        dic = {}\n",
    "        for i in range(len(numbers)):\n",
    "            \n",
    "            if numbers[i] in dic.keys():\n",
    "                if i+1!=dic[numbers[i]][1]:\n",
    "                    return [dic[numbers[i]][1],i+1]\n",
    "            dic[target - numbers[i]] = (numbers[i], i+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, numbers: List[int], target: int) -> List[int]:\n",
    "        length = len(numbers)\n",
    "        i = 0\n",
    "        j = length -1\n",
    "        while i<j:\n",
    "            if numbers[i] + numbers[j] == target:\n",
    "                return [i+1,j+1]\n",
    "            elif numbers[i] + numbers[j] > target:\n",
    "                j = j-1\n",
    "            else:\n",
    "                i = i+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, numbers: List[int], target: int) -> List[int]:\n",
    "        l,r = 0,len(numbers)-1\n",
    "\n",
    "        while l<r:\n",
    "            if numbers[l] + numbers[r] > target:\n",
    "                r-=1\n",
    "            elif numbers[l] + numbers[r] < target:\n",
    "                l+=1\n",
    "            else:\n",
    "                return [l+1,r+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        right = len(nums)-1\n",
    "        left = 0\n",
    "        while right>left:\n",
    "            if nums[right]+nums[left]<target:\n",
    "                left+=1\n",
    "            elif nums[right]+nums[left]>target:\n",
    "                right-=1\n",
    "            else:\n",
    "                return [left+1, right+1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, numbers: List[int], target: int) -> List[int]:\n",
    "        n = len(numbers)\n",
    "        i = 0\n",
    "        j = n - 1\n",
    "        while (i<j):\n",
    "            if numbers[i] + numbers[j] == target:\n",
    "                return [i+1, j+1]\n",
    "            elif numbers[i] + numbers[j] > target:\n",
    "                j -= 1\n",
    "            else:\n",
    "                i += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, numbers: List[int], target: int) -> List[int]:\n",
    "        # 用len()方法取得nums列表的长度\n",
    "        long = len(numbers)\n",
    "        #i取值从0到n（不包括n）\n",
    "        for i in range(long):\n",
    "            \n",
    "            k = target - numbers[i]\n",
    "            # 用count()函数查询nums列表中是否含有k\n",
    "            if numbers.count(k):\n",
    "                # 用index()函数取得k值在nums列表中的索引\n",
    "                # 加入i等于k的索引，则跳过，否则返回i和k的索引\n",
    "                if(i != numbers.index(k)):\n",
    "                    if i > numbers.index(k):\n",
    "                        return [numbers.index(k) + 1, i + 1]\n",
    "                    else:\n",
    "                        return [i + 1, numbers.index(k) + 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, numbers: List[int], target: int) -> List[int]:\n",
    "        for i in range(len(numbers)):\n",
    "            left = i+1\n",
    "            right = len(numbers)\n",
    "            while left<right:\n",
    "                mid = (left+right)//2\n",
    "                if numbers[i]+numbers[mid]==target:\n",
    "                    return [i+1,mid+1]\n",
    "                elif numbers[i]+numbers[mid]<target:\n",
    "                    left = mid+1\n",
    "                else:\n",
    "                    right = mid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, numbers: List[int], target: int) -> List[int]:\n",
    "        maps = dict()\n",
    "        for i, v in enumerate(numbers):\n",
    "            if target - v in maps:\n",
    "                return [maps[target-v]+1, i+1]\n",
    "            if v in maps:\n",
    "                continue\n",
    "            maps[v] = i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, numbers: List[int], target: int) -> List[int]:\n",
    "        d = {}\n",
    "        for i in range(len(numbers)):\n",
    "            res = target - numbers[i]\n",
    "            if res in d:\n",
    "                return [d[res]+1, i+1]\n",
    "            else:\n",
    "                d[numbers[i]] = i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, numbers: List[int], target: int) -> List[int]:\n",
    "        hash_tmp = dict()\n",
    "        for i in range(len(numbers)):\n",
    "            if hash_tmp.get(numbers[i]) is None:\n",
    "                hash_tmp[numbers[i]] = [i + 1]\n",
    "            else:\n",
    "                hash_tmp[numbers[i]] = hash_tmp[numbers[i]] + [i + 1]\n",
    "\n",
    "        res = []\n",
    "        i = 0\n",
    "        while i < len(numbers):\n",
    "            tmp = target - numbers[i]\n",
    "            if hash_tmp.get(tmp) is not None:\n",
    "                if tmp == numbers[i] and len(hash_tmp.get(tmp)) > 1:\n",
    "                    res.append(hash_tmp.get(numbers[i])[0])\n",
    "                    res.append(hash_tmp.get(numbers[i])[1])\n",
    "                    return res\n",
    "                else:\n",
    "                    res.append(hash_tmp.get(numbers[i])[0])\n",
    "                    res.append(hash_tmp.get(tmp)[0])\n",
    "                    return res\n",
    "            i += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, numbers: List[int], target: int) -> List[int]:\n",
    "        res = dict()\n",
    "        for i in range(len(numbers)):\n",
    "            index = res.get(numbers[i], [])\n",
    "            index.append(i+1)\n",
    "            res[numbers[i]] = index\n",
    "\n",
    "        for key in res:\n",
    "            a = res[key][0]\n",
    "            del res[key][0]\n",
    "            diff = target - key\n",
    "            index = res.get(diff, [])\n",
    "            if index:\n",
    "                b = index[0]\n",
    "                return [a, b]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, numbers: List[int], target: int) -> List[int]:\n",
    "        left = 0\n",
    "        right = len(numbers)- 1\n",
    "        while left < right:\n",
    "            if numbers[left] + numbers[right] == target:\n",
    "                return [left+1, right+1]\n",
    "            elif numbers[left] + numbers[right] < target:\n",
    "                left += 1\n",
    "            else:\n",
    "                right -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, numbers: List[int], target: int) -> List[int]:\n",
    "        \n",
    "        n = len(numbers)\n",
    "        \n",
    "        for i in range(n-1):\n",
    "            if numbers[i] == numbers[i+1] and numbers[i] + numbers[i+1] != target:\n",
    "                i += 1\n",
    "            else:\n",
    "                for j in range(i+1,n):\n",
    "                    if numbers[i]+numbers[j] == target:\n",
    "                        return [i+1,j+1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, numbers: List[int], target: int) -> List[int]:\n",
    "        n = len(numbers)\n",
    "        l, r = 0, n-1\n",
    "        while r >= l:\n",
    "            s = numbers[l] + numbers[r]\n",
    "            if s == target:\n",
    "                return [l+1, r+1]\n",
    "            elif s > target:\n",
    "                m = (l + r) // 2\n",
    "                s = numbers[l] + numbers[m]\n",
    "                if s == target:\n",
    "                    return [l+1, m+1]\n",
    "                elif s > target:\n",
    "                    r = m - 1\n",
    "                elif s < target:\n",
    "                    r -= 1\n",
    "            elif s < target:\n",
    "                m = (l + r) // 2\n",
    "                s = numbers[m] + numbers[r]\n",
    "                if s == target:\n",
    "                    return [m+1, r+1]\n",
    "                elif s > target:\n",
    "                    l += 1\n",
    "                elif s < target:\n",
    "                    l = m + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, numbers: List[int], target: int) -> List[int]:\n",
    "        a = []\n",
    "        for i in range(len(numbers)-1):\n",
    "            b = target - numbers[i]\n",
    "            if b in numbers[i+1:]:\n",
    "                a.append(i+1)\n",
    "                a.append(numbers[i+1:].index(b)+2+i)\n",
    "                return a\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def twoSum(self, numbers: List[int], target: int) -> List[int]:\r\n",
    "        l = 0\r\n",
    "        r = len(numbers) - 1\r\n",
    "        while l < r:\r\n",
    "            mid = l + (r - l) // 2\r\n",
    "            if numbers[l] + numbers[r] == target:\r\n",
    "                return [l+1, r+1]\r\n",
    "            elif numbers[l] + numbers[r] > target:\r\n",
    "                r -= 1\r\n",
    "            else:\r\n",
    "                l += 1\r\n",
    "        \r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, numbers: List[int], target: int) -> List[int]:\n",
    "        i,j = 0,len(numbers)-1\n",
    "        while i < j:\n",
    "            check = numbers[i] + numbers[j]\n",
    "            if check == target:\n",
    "                return i+1,j+1\n",
    "            elif check > target:\n",
    "                j -= 1\n",
    "            else:\n",
    "                i += 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, numbers: List[int], target: int) -> List[int]:\n",
    "        left = 0\n",
    "        right = len(numbers)-1\n",
    "\n",
    "        while left< right:\n",
    "            if numbers[left] + numbers[right] ==  target:\n",
    "                return [left+1, right+1]\n",
    "            elif numbers[left] + numbers[right] >  target:\n",
    "                right -= 1\n",
    "            else:\n",
    "                left += 1\n",
    "       \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, numbers: List[int], target: int) -> List[int]:\n",
    "        j = len(numbers)-1\n",
    "        i=0\n",
    "        n=len(numbers)\n",
    "        while n-1:\n",
    "            if numbers[i]+numbers[j] == target:\n",
    "                return[i+1, j+1]\n",
    "            elif numbers[i]+numbers[j]<target:\n",
    "                i+=1\n",
    "            else:\n",
    "                j-=1\n",
    "            n-=1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, numbers: List[int], target: int) -> List[int]:\n",
    "        i=0\n",
    "        while i <len(numbers):\n",
    "            try:\n",
    "                T = numbers[i+1:].index(target-numbers[i])+i+1\n",
    "                return [i+1, T+1]\n",
    "            except:\n",
    "                i+=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, numbers: List[int], target: int) -> List[int]:\n",
    "        low, high = 0, len(numbers) - 1\n",
    "        while low < high:\n",
    "            total = numbers[low] + numbers[high]\n",
    "            if total == target:\n",
    "                return [low + 1, high + 1]\n",
    "            elif total < target:\n",
    "                low += 1\n",
    "            else:\n",
    "                high -= 1\n",
    "\n",
    "        return [-1, -1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, numbers: List[int], target: int) -> List[int]:\n",
    "        n = len(numbers)\n",
    "        numbers.sort()\n",
    "        i, j = 0, n-1\n",
    "        while i < j:\n",
    "            v1, v2 = numbers[i], numbers[j]\n",
    "            if v1 + v2 == target:\n",
    "                return [i+1, j+1]\n",
    "            elif v1 + v2 > target:\n",
    "                j -=1\n",
    "            else:\n",
    "                i +=1\n",
    "        return [-1, -1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, numbers: List[int], target: int) -> List[int]:\n",
    "        i = 0\n",
    "        j = len(numbers) - 1\n",
    "        while 1:\n",
    "            if numbers[i] + numbers[j] == target:\n",
    "                return [i+1,j+1]\n",
    "            elif numbers[i] + numbers[j] < target:\n",
    "                i += 1\n",
    "            else:\n",
    "                j -= 1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
